24A - Ring road - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) ll a;cin>>a;
#define sin string s;cin>>s;
#define dia di(a)
#define dib di(b)
#define dic di(c)
#define dix di(x)
#define diy di(y)
#define diz di(z)
#define dik di(k)
#define din di(n)
#define dim di(m)
#define diq di(q)
#define endl '\n'
#define precise(i) cout<<fixed<<setprecision(i)
#define V vector<ll>
#define pb push_back
#define M map<ll,ll>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define back(x) x.rbegin(),x.rend()
#define MOD 1000000007
#define db double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N =998244353;

int vis[105];
int graph[105][105];
V g[105];

ll dfs(ll ver){
    ll ans=0,fl=0;
    vis[ver]=1;
    for(auto child:g[ver]){
        if(vis[child]) continue;
        fl=1;
        ans+=graph[ver][child];
        ans+=dfs(child);
    }
    if(!fl) ans = graph[ver][1];
    return ans;
}

int main(){
    fastio;

    ll T=1;
    // cin>>T;
    // int ogt=0;
    while(T--){
        // ogt++;
        din;
        ll sum=0;
        
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j <= n; ++j)
            {
                graph[i][j]=0;
            }
        }

        for (int i = 0; i < n; ++i)
        {
            dix;
            diy;
            dia;
            sum+=a;
            graph[x][y]=a;
            g[x].pb(y);
            g[y].pb(x);
        }

        ll cw = dfs(1);

        cout<<min(cw,sum-cw)<<endl;
        
       


    }
    return 0;
}